package com.yanceysong.codetop.s91_s100;

import java.util.Arrays;

public class S99_Easy_283_移动零 {
    /**
     * .S99_Easy_283_移动零
     * .<p>
     * .<a href="https://leetcode.cn/problems/move-zeroes/">...</a>
     * .<p>
     * .给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * .<p>
     * .请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     * .<p>
     * .示例：
     * .<p>
     * .输入: nums = [0,1,0,3,12]
     * .输出: [1,3,12,0,0]
     * .<p>
     * .输入: nums = [0]
     * .输出: [0]
     * .<p>
     * .提示：
     * .<p>
     * .1 <= nums.length <= 10^4
     * .-2^31 <= nums[i] <= 2^31 - 1
     * .<p>
     * .核心标签：数组、双指针
     * .<p>
     * .算法原理：双指针法
     * .- 使用两个指针：left（慢指针）和 right（快指针）
     * .- left 指针指向下一个非零元素应该放置的位置
     * .- right 指针遍历整个数组，寻找非零元素
     * .- 当 right 指向非零元素时，交换 left 和 right 位置的元素
     * .- 交换后，left 指针右移，继续寻找下一个非零元素的位置
     * .- right 指针持续右移，直到遍历完整个数组
     * .<p>
     * .关键洞察：
     * .1. 双指针法可以在一次遍历中完成操作，时间复杂度 O(n)
     * .2. left 指针维护的是"非零元素区域"的边界
     * .3. 当 left == right 时，说明前面没有零，交换自己和自己不影响结果
     * .4. 当 left < right 时，交换会将非零元素移到前面，零元素移到后面
     * .5. 保持相对顺序：因为 left 和 right 都是从左到右移动，不会打乱非零元素的顺序
     * .<p>
     * .图解示例：nums = [0,1,0,3,12]
     * .<p>
     * .初始状态：
     * .[0, 1, 0, 3, 12]
     * .L
     * .R
     * .<p>
     * .步骤1：right 指向 0，不交换，right 右移
     * .[0, 1, 0, 3, 12]
     * .L  R
     * .<p>
     * .步骤2：right 指向 1（非零），交换 left 和 right
     * .[1, 0, 0, 3, 12]
     * .L  R
     * .交换后，left 右移
     * .[1, 0, 0, 3, 12]
     * .L  R
     * .<p>
     * .步骤3：right 右移，指向 0，不交换
     * .[1, 0, 0, 3, 12]
     * .L     R
     * .<p>
     * .步骤4：right 右移，指向 3（非零），交换 left 和 right
     * .[1, 3, 0, 0, 12]
     * .L     R
     * .交换后，left 右移
     * .[1, 3, 0, 0, 12]
     * .L        R
     * .<p>
     * .步骤5：right 右移，指向 12（非零），交换 left 和 right
     * .[1, 3, 12, 0, 0]
     * .L        R
     * .交换后，left 右移
     * .[1, 3, 12, 0, 0]
     * .L           R
     * .<p>
     * .步骤6：right 到达数组末尾，结束
     * .<p>
     * .最终结果：[1, 3, 12, 0, 0]
     * .<p>
     * .详细过程图解：
     * .<p>
     * .原始数组：[0, 1, 0, 3, 12]
     * .<p>
     * .right = 0: nums[0] = 0，跳过
     * .left = 0, right = 0
     * .[0, 1, 0, 3, 12]
     * .<p>
     * .right = 1: nums[1] = 1 ≠ 0，交换 nums[0] 和 nums[1]
     * .left = 0, right = 1
     * .[0, 1, 0, 3, 12] → [1, 0, 0, 3, 12]
     * .left++，left = 1
     * .<p>
     * .right = 2: nums[2] = 0，跳过
     * .left = 1, right = 2
     * .[1, 0, 0, 3, 12]
     * .<p>
     * .right = 3: nums[3] = 3 ≠ 0，交换 nums[1] 和 nums[3]
     * .left = 1, right = 3
     * .[1, 0, 0, 3, 12] → [1, 3, 0, 0, 12]
     * .left++，left = 2
     * .<p>
     * .right = 4: nums[4] = 12 ≠ 0，交换 nums[2] 和 nums[4]
     * .left = 2, right = 4
     * .[1, 3, 0, 0, 12] → [1, 3, 12, 0, 0]
     * .left++，left = 3
     * .<p>
     * .right = 5: 超出数组范围，结束
     * .<p>
     * .最终结果：[1, 3, 12, 0, 0]
     * .<p>
     * .另一个示例：nums = [1,2,3,0,0]
     * .<p>
     * .初始：[1, 2, 3, 0, 0]
     * .L
     * .R
     * .<p>
     * .right = 0: nums[0] = 1 ≠ 0，交换（自己和自己）
     * .[1, 2, 3, 0, 0]
     * .L
     * .R
     * .left++
     * .<p>
     * .right = 1: nums[1] = 2 ≠ 0，交换（自己和自己）
     * .[1, 2, 3, 0, 0]
     * .L
     * .R
     * .left++
     * .<p>
     * .right = 2: nums[2] = 3 ≠ 0，交换（自己和自己）
     * .[1, 2, 3, 0, 0]
     * .L
     * .R
     * .left++
     * .<p>
     * .right = 3: nums[3] = 0，跳过
     * .[1, 2, 3, 0, 0]
     * .L
     * .R
     * .<p>
     * .right = 4: nums[4] = 0，跳过
     * .[1, 2, 3, 0, 0]
     * .L
     * .R
     * .<p>
     * .结果：[1, 2, 3, 0, 0]（没有变化）
     * .<p>
     * .双指针的工作原理：
     * .<p>
     * .┌─────────────────────────────────────┐
     * .│  [非零元素区域] [待处理区域] [零]   │
     * .│         ↑              ↑             │
     * .│       left          right            │
     * .└─────────────────────────────────────┘
     * .<p>
     * .- left 左边：已处理的非零元素
     * .- left 到 right 之间：零元素
     * .- right 及右边：待处理的元素
     * .<p>
     * .时间复杂度：O(n)，其中 n 为数组长度
     * .- 只需要遍历数组一次，right 指针从 0 移动到 n-1
     * .<p>
     * .空间复杂度：O(1)
     * .- 只使用了常数个变量，原地修改数组
     */
    public void moveZeroes(int[] nums) {
        int arrayLength = nums.length;

        // left 指针：指向下一个非零元素应该放置的位置
        int leftPointer = 0;

        // right 指针：遍历整个数组
        int rightPointer = 0;

        // 遍历数组
        while (rightPointer < arrayLength) {
            // 如果 right 指向的元素不是 0
            if (nums[rightPointer] != 0) {
                // 交换 left 和 right 位置的元素
                // 这样可以将非零元素移到前面，零元素移到后面
                swap(nums, leftPointer, rightPointer);

                // left 指针右移，指向下一个非零元素应该放置的位置
                leftPointer++;
            }

            // right 指针持续右移，继续遍历
            rightPointer++;
        }
    }

    /**
     * .交换数组中两个位置的元素
     *
     * .@param nums  数组
     * .@param left  第一个位置
     * .@param right 第二个位置
     */
    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    public static void main(String[] args) {
        S99_Easy_283_移动零 solution = new S99_Easy_283_移动零();

        System.out.println("=== 移动零测试开始 ===");

        // 测试1: 题目示例1 - [0,1,0,3,12]
        System.out.println("\n--- 测试1: [0,1,0,3,12] ---");
        testCase1(solution);

        // 测试2: 题目示例2 - [0]
        System.out.println("\n--- 测试2: [0] ---");
        testCase2(solution);

        // 测试3: 没有零
        System.out.println("\n--- 测试3: 没有零 [1,2,3,4,5] ---");
        testNoZeros(solution);

        // 测试4: 全是零
        System.out.println("\n--- 测试4: 全是零 [0,0,0,0] ---");
        testAllZeros(solution);

        // 测试5: 零在开头
        System.out.println("\n--- 测试5: 零在开头 [0,0,0,1,2,3] ---");
        testZerosAtStart(solution);

        // 测试6: 零在末尾
        System.out.println("\n--- 测试6: 零在末尾 [1,2,3,0,0,0] ---");
        testZerosAtEnd(solution);

        // 测试7: 零在中间
        System.out.println("\n--- 测试7: 零在中间 [1,0,2,0,3] ---");
        testZerosInMiddle(solution);

        // 测试8: 单个非零元素
        System.out.println("\n--- 测试8: 单个非零元素 [1] ---");
        testSingleNonZero(solution);

        // 测试9: 交替的零和非零
        System.out.println("\n--- 测试9: 交替的零和非零 [0,1,0,2,0,3] ---");
        testAlternating(solution);

        // 测试10: 负数
        System.out.println("\n--- 测试10: 负数 [-1,0,-2,0,-3] ---");
        testNegativeNumbers(solution);

        // 测试11: 大数组
        System.out.println("\n--- 测试11: 大数组 ---");
        testLargeArray(solution);

        // 测试12: 只有一个零在开头
        System.out.println("\n--- 测试12: 只有一个零在开头 [0,1,2,3] ---");
        testSingleZeroAtStart(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1: [0,1,0,3,12]
     * .期望输出：[1,3,12,0,0]
     */
    private static void testCase1(S99_Easy_283_移动零 solution) {
        int[] nums = {0, 1, 0, 3, 12};
        int[] expected = {1, 3, 12, 0, 0};

        System.out.println("输入: " + Arrays.toString(nums));
        solution.moveZeroes(nums);
        System.out.println("输出: " + Arrays.toString(nums));
        System.out.println("期望: " + Arrays.toString(expected));

        assert Arrays.equals(nums, expected) : "测试1失败";
        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试2: [0]
     * .期望输出：[0]
     */
    private static void testCase2(S99_Easy_283_移动零 solution) {
        int[] nums = {0};
        int[] expected = {0};

        System.out.println("输入: " + Arrays.toString(nums));
        solution.moveZeroes(nums);
        System.out.println("输出: " + Arrays.toString(nums));
        System.out.println("期望: " + Arrays.toString(expected));

        assert Arrays.equals(nums, expected) : "测试2失败";
        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试3: 没有零 [1,2,3,4,5]
     * .期望输出：[1,2,3,4,5]
     */
    private static void testNoZeros(S99_Easy_283_移动零 solution) {
        int[] nums = {1, 2, 3, 4, 5};
        int[] expected = {1, 2, 3, 4, 5};

        System.out.println("输入: " + Arrays.toString(nums));
        solution.moveZeroes(nums);
        System.out.println("输出: " + Arrays.toString(nums));
        System.out.println("期望: " + Arrays.toString(expected));

        assert Arrays.equals(nums, expected) : "测试3失败";
        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试4: 全是零 [0,0,0,0]
     * .期望输出：[0,0,0,0]
     */
    private static void testAllZeros(S99_Easy_283_移动零 solution) {
        int[] nums = {0, 0, 0, 0};
        int[] expected = {0, 0, 0, 0};

        System.out.println("输入: " + Arrays.toString(nums));
        solution.moveZeroes(nums);
        System.out.println("输出: " + Arrays.toString(nums));
        System.out.println("期望: " + Arrays.toString(expected));

        assert Arrays.equals(nums, expected) : "测试4失败";
        System.out.println("✓ 测试4通过");
    }

    /**
     * .测试5: 零在开头 [0,0,0,1,2,3]
     * .期望输出：[1,2,3,0,0,0]
     */
    private static void testZerosAtStart(S99_Easy_283_移动零 solution) {
        int[] nums = {0, 0, 0, 1, 2, 3};
        int[] expected = {1, 2, 3, 0, 0, 0};

        System.out.println("输入: " + Arrays.toString(nums));
        solution.moveZeroes(nums);
        System.out.println("输出: " + Arrays.toString(nums));
        System.out.println("期望: " + Arrays.toString(expected));

        assert Arrays.equals(nums, expected) : "测试5失败";
        System.out.println("✓ 测试5通过");
    }

    /**
     * .测试6: 零在末尾 [1,2,3,0,0,0]
     * .期望输出：[1,2,3,0,0,0]
     */
    private static void testZerosAtEnd(S99_Easy_283_移动零 solution) {
        int[] nums = {1, 2, 3, 0, 0, 0};
        int[] expected = {1, 2, 3, 0, 0, 0};

        System.out.println("输入: " + Arrays.toString(nums));
        solution.moveZeroes(nums);
        System.out.println("输出: " + Arrays.toString(nums));
        System.out.println("期望: " + Arrays.toString(expected));

        assert Arrays.equals(nums, expected) : "测试6失败";
        System.out.println("✓ 测试6通过");
    }

    /**
     * .测试7: 零在中间 [1,0,2,0,3]
     * .期望输出：[1,2,3,0,0]
     */
    private static void testZerosInMiddle(S99_Easy_283_移动零 solution) {
        int[] nums = {1, 0, 2, 0, 3};
        int[] expected = {1, 2, 3, 0, 0};

        System.out.println("输入: " + Arrays.toString(nums));
        solution.moveZeroes(nums);
        System.out.println("输出: " + Arrays.toString(nums));
        System.out.println("期望: " + Arrays.toString(expected));

        assert Arrays.equals(nums, expected) : "测试7失败";
        System.out.println("✓ 测试7通过");
    }

    /**
     * .测试8: 单个非零元素 [1]
     * .期望输出：[1]
     */
    private static void testSingleNonZero(S99_Easy_283_移动零 solution) {
        int[] nums = {1};
        int[] expected = {1};

        System.out.println("输入: " + Arrays.toString(nums));
        solution.moveZeroes(nums);
        System.out.println("输出: " + Arrays.toString(nums));
        System.out.println("期望: " + Arrays.toString(expected));

        assert Arrays.equals(nums, expected) : "测试8失败";
        System.out.println("✓ 测试8通过");
    }

    /**
     * .测试9: 交替的零和非零 [0,1,0,2,0,3]
     * .期望输出：[1,2,3,0,0,0]
     */
    private static void testAlternating(S99_Easy_283_移动零 solution) {
        int[] nums = {0, 1, 0, 2, 0, 3};
        int[] expected = {1, 2, 3, 0, 0, 0};

        System.out.println("输入: " + Arrays.toString(nums));
        solution.moveZeroes(nums);
        System.out.println("输出: " + Arrays.toString(nums));
        System.out.println("期望: " + Arrays.toString(expected));

        assert Arrays.equals(nums, expected) : "测试9失败";
        System.out.println("✓ 测试9通过");
    }

    /**
     * .测试10: 负数 [-1,0,-2,0,-3]
     * .期望输出：[-1,-2,-3,0,0]
     */
    private static void testNegativeNumbers(S99_Easy_283_移动零 solution) {
        int[] nums = {-1, 0, -2, 0, -3};
        int[] expected = {-1, -2, -3, 0, 0};

        System.out.println("输入: " + Arrays.toString(nums));
        solution.moveZeroes(nums);
        System.out.println("输出: " + Arrays.toString(nums));
        System.out.println("期望: " + Arrays.toString(expected));

        assert Arrays.equals(nums, expected) : "测试10失败";
        System.out.println("✓ 测试10通过");
    }

    /**
     * .测试11: 大数组
     * .期望输出：非零元素在前，零在后
     */
    private static void testLargeArray(S99_Easy_283_移动零 solution) {
        int[] nums = new int[100];
        // 前50个元素为非零（1-50），后50个元素为0
        for (int i = 0; i < 50; i++) {
            nums[i] = i + 1;
        }

        System.out.println("输入: [1,2,...,50,0,0,...,0] (50个非零 + 50个零)");
        solution.moveZeroes(nums);
        System.out.print("输出: [");
        for (int i = 0; i < 10; i++) {
            System.out.print(nums[i] + (i < 9 ? "," : ""));
        }
        System.out.println(",...] (前50个为1-50，后50个为0)");

        // 验证前50个元素是1-50
        for (int i = 0; i < 50; i++) {
            assert nums[i] == i + 1 : "前50个元素应该是1-50";
        }
        // 验证后50个元素是0
        for (int i = 50; i < 100; i++) {
            assert nums[i] == 0 : "后50个元素应该是0";
        }

        System.out.println("✓ 测试11通过");
    }

    /**
     * .测试12: 只有一个零在开头 [0,1,2,3]
     * .期望输出：[1,2,3,0]
     */
    private static void testSingleZeroAtStart(S99_Easy_283_移动零 solution) {
        int[] nums = {0, 1, 2, 3};
        int[] expected = {1, 2, 3, 0};

        System.out.println("输入: " + Arrays.toString(nums));
        solution.moveZeroes(nums);
        System.out.println("输出: " + Arrays.toString(nums));
        System.out.println("期望: " + Arrays.toString(expected));

        assert Arrays.equals(nums, expected) : "测试12失败";
        System.out.println("✓ 测试12通过");
    }
}

